#include<cstdlib>
#include<iostream>
#include<limits>


#define RED true
#define BLACK false
#define MIN (std::numeric_limits<double>::min())

struct section              //定义一个结构section来储存区间端点
{
    double low;
    double high;
};

class IntervalTree      //该区间树的delete函数以及析构函数尚未完成，但老师似乎也没有要求（手动狗头U•ェ•*U
{
public:
    class Node          //区间树的节点，含有section类型的区间，以及红黑树所需的左右孩子，父母，颜色，同时加入了一个拓展数据max，用来子树中最大区间右端点
    {
        public:
        section interval;
        double max;
        Node* lc;
        Node* rc;
        Node* parent;
        bool color;
        Node(){color = RED;};
        Node(section _interval)
        {
            interval = _interval;
            max = _interval.high;
            lc = rc = parent = NULL;
            color = RED;
        };
    };

protected:
    Node* root;             //一颗红黑树所需的根和nil节点
    Node* nil;
    //void transplant(Node* _u, Node* _v);
    void RightRotate(Node* _x);
    void LeftRotate(Node* _x);
    //void release(Node* _x);
    void insert(Node* _x);              //这是内部函数，此次插入保证了相关max的值合法，但不涉及红黑平衡
    //Node* successor(Node* _x) const;
    //Node* predecessor(Node* _x) const;
    //Node* min(Node* _x) const;
    //Node* max(Node* _x) const;

public:
    IntervalTree() 
    {
        nil = new Node;
        nil->color = BLACK;
        nil->interval.high = MIN;
        nil->interval.low = MIN;
        root = nil;
    };
    //~IntervalTree();
    Node* getroot(){return root;};
    int interval_insert(double _low, double _high);     //在前面insert的基础上再保证红黑，实现最终的区间树插入
    int interval_insert(Node* _new);
    Node* interval_search(section _i);              //区间树搜索，原理与王老师讲义上相同，不再赘述U•ェ•*U
    Node* interval_search(double _low, double _high);
    //int del(Node* _x);
};

/*
void IntervalTree::release(Node* _x)
{
    if(_x != NULL)
    {
        release(_x->lc);
        release(_x->rc);
        delete _x;
    }
};

IntervalTree::~IntervalTree()
{
    release(root);
};
*/

void IntervalTree::insert(Node* _x)
{
    Node* y = this->nil;
    Node* x = this->root;
    _x->lc = _x->rc = this->nil;
    while(x != this->nil)
    {
        y = x;
        x->max = (x->max > _x -> max) ? x->max : _x->max;
        if(_x->interval.low < x->interval.low)
            x = x->lc;
        else
            x = x->rc;
    }
    _x->parent = y;
    if(y == this->nil)
        this->root = _x;
    else if(_x->interval.low < y->interval.low)
        y->lc = _x;
    else
    {
        y->rc = _x;
    }
};

int IntervalTree::interval_insert(Node* _new)
{
    Node* x = _new;
    if(this->root == this->nil)
    {
        this->root = x;
        this->root->color = BLACK;
        return 0;
    }
    insert(x);
    if(x->parent->color == BLACK)
    {
        this->root->color = BLACK;
        return 0;
    }
    while(x->parent != this->nil && x->parent->color == RED)
    {
        if(x->parent == x->parent->parent->lc)
        {
            Node* y = x->parent->parent->rc;
            if(y != this->nil && y->color == RED)
            {
                x->color = RED;
                x->parent->color = y->color = BLACK;
                y->parent->color = RED;
                x = y->parent;
            }
            else
            {
                if(x == x->parent->rc)
                {
                    this->LeftRotate(x->parent);
                    x = x->lc;
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                this->RightRotate(x->parent->parent);
            }
        }
        else if(x->parent == x->parent->parent->rc)
        {
            Node* y = x->parent->parent->lc;
            if(y != this->nil && y->color == RED)
            {
                x->color = RED;
                x->parent->color = y->color = BLACK;
                y->parent->color = RED;
                x = y->parent;
            }
            else
            {
                if(x == x->parent->lc)
                {
                    this->RightRotate(x->parent);
                    x = x->rc;
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                this->LeftRotate(x->parent->parent);
            }
        }
    }
    return 0;
};

int IntervalTree::interval_insert(double _low, double _high)
{
    section x;
    x.low = _low;
    x.high = _high;
    Node *t = new Node(x);
    insert(t);
    return 0;
};

IntervalTree::Node* IntervalTree::interval_search(section _i)
{
    Node* x = this->root;
    while(x != this->nil && (_i.low > x->interval.high || x->interval.low > _i.high))
    {
        if(x->lc != nil && _i.low <= x->lc->max)
            x = x->lc;
        else
        {
            x = x->rc;
        }
    }
    return x;
};

IntervalTree::Node* IntervalTree::interval_search(double _low, double _high)
{
    section x;
    x.low = _low;
    x.high = _high;
    return interval_search(x);
};

void IntervalTree::RightRotate(Node* _x)
{
    Node* y = _x->lc;
    _x->lc = y->rc;
    if(y->rc != nil)
        y->rc->parent = _x;
    y->parent = _x->parent;
    if(_x->parent == nil)
        root = y;
    else if (_x == _x->parent->lc)
        _x->parent->lc = y;
    else
        _x->parent->rc = y;
    y->rc = _x;
    _x->parent = y;
    y->max = _x->max;
    double tmp = (_x->lc->max > _x->rc->max) ? _x->lc->max : _x->rc->max;
    _x->max = (_x->interval.high > tmp) ? _x->interval.high : tmp;
};

void IntervalTree::LeftRotate(Node* _x)
{
    Node* y = _x->rc;
    _x->rc = y->lc;
    if(y->lc != nil)
        y->lc->parent = _x;
    y->parent = _x->parent;
    if(_x->parent == nil)
        root = y;
    else if (_x == _x->parent->lc)
        _x->parent->lc = y;
    else
        _x->parent->rc = y;
    y->lc = _x;
    _x->parent = y;
    y->max = _x->max;
    double tmp = (_x->lc->max > _x->rc->max) ? _x->lc->max : _x->rc->max;
    _x->max = (_x->interval.high > tmp) ? _x->interval.high : tmp;
};